/**
 * https://leetcode.cn/submissions/detail/582422748/
 * 547. 省份数量
 * Medium, 黄伟杰 2024.11.22
 * 并查集
 */

class union_find
{
    vector<int> parent;
    int group;

public:
    // 构造从 0 到 n - 1 的节点
    union_find(int n) : parent(n), group()
    {
        for (int i = 0; i < n; ++i)
        {
            parent[i] = i;
        }
        group = n;
    }

    // 合并两个节点
    void pair(int index1, int index2)
    {
        int root_1 = find(index1), root_2 = find(index2);
        if (root_1 != root_2)
        {
            --group;
        }
        parent[root_2] = root_1;
    }

    // 找到根节点
    int find(int index)
    {
        vector<int> temp;

        int root = index;
        for (; parent[root] != root; root = parent[root])
        {
            temp.emplace_back(root);
        }

        for (auto &it : temp)
        {
            parent[it] = root;
        }

        return root;
    }

    // 判断连接性
    bool check(int index1, int index2)
    {
        return find(index1) == find(index2);
    }

    // 返回连通图的数量
    int group_count()
    {
        return group;
    }
};
class Solution
{
public:
    int findCircleNum(vector<vector<int>> &isConnected)
    {
        union_find x(isConnected.size());

        for (int i = 0; i < isConnected.size(); i++)
        {
            for (int j = 0; j < isConnected[0].size(); j++)
            {
                if (isConnected[i][j])
                {
                    x.pair(i, j);
                }
            }
        }
        return x.group_count();
    }
};